# 将有序数组转化为平衡二叉搜索树
# 按照中序恢复二叉树，且将中间元素作为根节点


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        
        self.val = val
        self.left = left
        self.right = right


class Solution:

    def sortedArrayToBST(self, nums: list):

        if not nums:
            return None
        
        m = len(nums) // 2
        left = self.sortedArrayToBST(nums[0:m])
        right = self.sortedArrayToBST(nums[m+1:])

        return TreeNode(nums[m], left, right)
    




if __name__ == "__main__":

    arr = [-10,-3,0,5,9]

    
    sol = Solution()
    root = sol.sortedArrayToBST(arr)












